// @algorithm @lc id=100315 lang=cpp
// @title er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    bool verifyPostorder(vector<int> &postorder) {
        return helper(postorder, 0, postorder.size() - 1);
    }
    // left和right为树的后序遍历的起始和结束坐标
    bool helper(vector<int> &postorder, int left, int right) {
        // 空树和只有根节点的树返回true
        if (left >= right) {
            return true;
        }
        // temp为移动指针，找到左子树的边界，为m-1
        int temp = left;
        while (postorder[temp] < postorder[right]) {
            ++temp;
        }
        // m为右子树的起点
        int m = temp;
        // temp找到第一个不大于根节点的位置，如果树为二叉搜索树，那么temp在right结束
        while (postorder[temp] > postorder[right]) {
            ++temp;
        }
        // temp==right，证明此次验证成功，接下来验证左子树和右子树
        return temp == right && helper(postorder, left, m - 1) && helper(postorder, m, right - 1);
    }
};